package org.example.sulotion;

public class 最长连续子数组 {

    public static void main(String[] args) {

        int[] nums={-2,1,-3,4,-1,2,1,-5,4};
//        int[] nums={-2,-3,-1,-5};
//        int len = maxSubArray(nums);
//        int len = maxSubArray2(nums);
        int len = maxSubArray3(nums);
        System.out.println(len);
    }

    //贪心算法
    public static int maxSubArray(int[] nums){
        int max=Integer.MIN_VALUE;
        int sum=0;
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            sum+=nums[i];
            max = Math.max(sum, max);
            //如果小于0，就去掉前面的，继续往后走
            if(sum<0){
                sum=0;
            }
        }
        return max;
    }

    //动态规划
    public static int maxSubArray2(int[] nums) {
        int max=nums[0];
        int pre=0;  //之前元素
        for (int i = 0; i <nums.length ; i++) {
            //若之前元素大于0，则当前元素加上之前元素,并赋值给之前元素，否则,把当前元素赋给之前元素
            nums[pre]=Math.max(nums[i],nums[i]+nums[pre]);
            max=Math.max(max,nums[pre]);
        }
        return max;
    }

    public static int maxSubArray3(int[] nums) {
        int res = nums[0];
        int sum = 0;
        for (int num : nums) {
            if (sum > 0)
                sum += num;
            else
                sum = num;     //如果之前sum是负数，则把之后大于0的数直接赋给它，并往后寻找最长子数组
            res = Math.max(res, sum);
        }
        return res;
    }
}
